#include <iostream>
#include <stack>
#include <string>

using namespace std;

//为什么第一反应用栈解题？
//遇到“撤销上一步”“回退”这种特性，第一时间想到栈

class Solution 
{
public:
	bool backspaceCompare(string s, string t) 
	{
		return buildString(s) == buildString(t);		//重载等号，按照字符序列逐个比较
	}
	
private:
	string buildString(string str) 
	{
		stack<char> st;			//模拟文本输入和退格过程，保存有效字符
		
		for (char c : str)		//C++11中的base-for循环用法
		{
			if (c == '#') 
			{
				if (!st.empty()) 
				{
					st.pop();
				}
			}
			else 
			{
				st.push(c);
			}
		}
		
		string result;			//保存最终处理结果
		while (!st.empty()) 
		{
			result = st.top() + result;		//想要重新拼接成原来的文本结果，只能反着拼接
			st.pop();
		}
		
		return result;
	}
};	

int main() 
{
	Solution sol;
	string s, t;
	
	cout << "请输入字符串 s: ";
	cin >> s;
	cout << "请输入字符串 t: ";
	cin >> t;
	
	bool result = sol.backspaceCompare(s, t);
	
	if (result) 
	{
		cout << "true" << endl;
	}
	else 
	{
		cout << "false" << endl;
	}
	
	return 0;
}

